/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package BookManager;
//import DrakeSources.ArrayList;
import java.io.*;
//Import for use w/ randomizeBooks()
import java.util.Random;

/**
 *
 * @author mif
 */
public class BookArray {
    private Book[] books;
    private int size;
    
    /**====================================================================**/
    /**
     * Constructor.
     * @param startingCapacity 
     */
    public BookArray(int startingCapacity) {
	books = new Book[startingCapacity];
	size = 0;
    }
    
    
    /*
     * Makes a copy of BookArray
     * 
     * by Ilya Ivanov
     * 
     */
    public BookArray copy() {
        BookArray ba = new BookArray(this.size);

	for(int i = 0; i < size; i++) { 
	    ba.add(books[i]);
	}
        
        return ba;
    }
    
    
    /**====================================================================**/
    /**
     * Add a book to the array.
     * @param b 
     */
    public void add(Book b) {
	if(isFull()) { //check if we're full
	    stretchArray(); //bump the size if we are
	}
	
	books[size] = b; //add our new element to the end of the array
	size++;
    }
    
    /**
     * Get the current book array size.
     * @return 
     */
    public int size() {
	return size;
    }
    
    /**
     * remove the book at index b
     * @param index
     * @return 
     */
    public boolean remove(int index) {
	System.out.println("remove not yet implemented");
	System.exit(1);
	return false;
    }
    
    /**
     * Increase the size of our array.
     */
    protected void stretchArray() {
	//allocate double our current space
	//notice we use length instead of size -- we double what we actually have
	Book[] newBook = new Book[books.length * 2]; 
	
	for(int i = 0; i < size; i++) { //copy books to new array
	    newBook[i] = books[i];
	}
	books = newBook; //assign new array to our object var
    }
    
    /**
     * Check if we're full
     * @return 
     */
    protected boolean isFull() {
	if(books.length == size) {
	    return true;
	}
	else {
	    return false;
	}
    }

    
    public String toString() {
	String s = "";
	for(int i = 0; i < size; i++) {
	    s += books[i];  //Book has toString now! --mif
	    s += "\n"; //newline separator
	}
	
	return s;
    }
    
    /**
     * randomize the book order. This is meant to aid in testing.
     * 
     * implemented by Ryan Maestro
     */
    public void randomizeBooks() {    
        Random rnd = new Random(133713371337L); //seeded for "deterministic randomness"

        for (int i = size - 1; i > 0; i--)
	{
	     // Set elementB as a random position
	     int elementB = rnd.nextInt(size - 1);

	    // Switch the element at i with the element at elementB
	     swap(i, elementB);
	}
	
    }
    
    /** bubbleSort()
     *  Sort the book array by Title using bubbleSort()
     *  Implemented by Ilya Ivanov
     */
    public long bubbleSort() {
	Globals.zeroAll();
	Globals.setMem(size);
	
	bubbleSort(true);
	return Globals.Actions;
    }
    
    //overloading this function allows us to avoid refactoring code
    //i.e., existing method calls that don't pass a parameter will now have
    //the return value available.
    public void bubbleSort(boolean called) {
        int outer, inner;
        
	
        for(outer = size - 1; outer > 1; outer--) {
	    Globals.Actions+=2;//for-loop comparison and increment, once for each iteration
            for(inner = 0; inner < outer; inner++) {
		Globals.Actions++;//for-loop comparison, once for each iteration
		Globals.Actions++;//if statement comparison (below)
                if(books[inner].getTitle().compareTo(books[inner+1].getTitle()) < 0) {
                    swap(inner, inner+1);
                }
            }
        }
    
    }
    
    private void swap(int j, int k) {
	Globals.Actions+=3;//swap action is three copies
	Globals.incMem(); //swap uses a temp var
	
        Book temp = books[j].copy();
        books[j] = books[k];
        books[k] = temp;

	Globals.decMem(); //done with temp var
    }
    
    /** insertionSort()
     *  Sort the book array by Title using insertionSort()
     * Implemented by Maryann Musselman
     */
    public long insertionSort() {
	Globals.zeroAll();
	Globals.setMem(size);
	insertionSort(true);
	return Globals.Actions;
    }
    public void insertionSort(boolean called) {
	Book temp;		 // comparison variable; unsorted array
	Globals.incMem();
	
	int j;		    // comparison variable; sorted array
	
	for (int i = 1; i < (size-1); i++)		
	{
		Globals.Actions++; //for loop comparison
		
		temp = books[i];			  // obtain first element in unsorted array
		Globals.Actions++; //assignment
		
		j = i - 1;			        // index # of the last sorted element
		Globals.Actions++;//assignment
		
		while ((j >= 0) && (temp.getTitle().compareTo(books [j].getTitle()) < 0))	// while current sorted element > unsorted element
		{
			Globals.Actions+=2; //two comparisons per iteration
			
			books[j + 1] = books[j];		
			Globals.Actions++;  //assignment
			
			j--;					
			Globals.Actions++; //decrement
		}
      
		books[j + 1] = temp;	
		Globals.Actions++; //assignment
	}
	
	Globals.decMem(); //done with temp
    }

    /**====================================================================**/
    /**mergeSort()
     * Sort the book array by title using Merge Sort.
     * Implemented by Maxwell French
     * 
     */
    public long mergeSort() {
	Globals.zeroAll();
	Globals.setMem(size);
	mergeSort(true);
	return Globals.Actions;
    }
    
    public void mergeSort(boolean called) {
	books = mergeSortH(0, size - 1);
	Globals.Actions++; //assignment
    }
    
    protected Book[] mergeSortH(int bottom, int top) {
	Globals.Actions++; //comparison, below
	if(bottom == top) {
	    Book[] b = new Book[]{books[bottom]};
	    Globals.Actions++; //assignment
	    
	    return b;
	}
	else {
	    int middle = (bottom + top) / 2;
	    Globals.Actions++; //assignment (above)
	    
	    return merge(mergeSortH(bottom, middle), mergeSortH(middle + 1, top));
	}
    }
    
    protected Book[] merge(Book[] books1, Book[] books2) {
	Book[] result = new Book[books1.length + books2.length];
	
	long memTemp = Globals.Memory; //save this value
	Globals.addMem(books1.length + books2.length);
	
	int i = 0;
	int j = 0;
	for(int k = 0; k < result.length; k++) {
	    Globals.Actions++; //for loop comparison
	    
	    Globals.Actions+=3; //comparison (below)
	    if((j == books2.length) || 
		    ((i < books1.length) 
		    && (books1[i].getTitle().compareTo(books2[j].getTitle()) <= 0))) {  //we use string compareTo to see how they differ
		
		result[k] = books1[i];
		Globals.Actions++; //assignment
		
		i++;
		Globals.Actions++; //increment
	    }
	    else {
		result[k] = books2[j];
		Globals.Actions++; //assignment
		
		j++;
		Globals.Actions++; //increment
	    }
	}
	
	//note that we don't free the result array yet, technically
	//it'd be impossible to do when it actually happens (after the recursion rewinds)
	Globals.setMem(memTemp);
	return result;
    }
} 
